# coding = UTF-8
# @Time : 2022/01/03 08:23
# @Author : PP_YY
# @File : Elgamal.py
# @Descrision : 密码学课程设计
# 为简化问题，我们取p=19,g=2,私钥x=9,则公钥y=29 mod 19=18。
# 消息m的ELGamal签名为(r,s),其中r=gk mod p,s=(h(m)-xr)k-1 mod (p-1)
import random
import numpy


def Mutli_big(a,n,p): #高阶模乘,a^n mod p
    m = bin(int(n))[2:][::-1]
    k = len(m)-1
    d = 1
    for i in range(k,-1,-1):
        d = (d*d)%p
        if m[i] == "1":
            d = (d*a)%p
    return d


def Fermat(num): #费马小定理
    for _ in range(20):
        b = random.randint(1, num-1)
        if numpy.gcd(num,b) != 1:
          return False
        if Mutli_big(b,num-1,num) !=1:
          return False
    return True
        

def Miller_rabin(num):# Miller_rubin素数判断
    t = 0
    m = num-1
    while m%2 == 0:
        t += 1
        m /= 2
    for _ in range(20):
        b = random.randint(1, num-1)
        s = 0
        z = Mutli_big(b, m, num)
        if z == 1 or z == num-1:
            continue
        while s != t:
            s += 1
            z = Mutli_big(z, 2, num)
            if z == 1:
                return False
            if z == num - 1:
                break
        if s == t:
            return False
        continue
    return True


def is_prime(num):
    if num <= 1:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    if Miller_rabin(num):
        return True
    return False


def choose_p():
    p = random.randint(2,1000000000000000000)
    while not(is_prime(p)):
        p = random.randint(2, 1000000000000000000)
    return p


# def calculate_a(p): 算的是阶
    # Fi_p = p-1
    # s = 0
    # for i in range(1,p):
        # for j in range(1,p):
            # s = j
            # if Mutli_big(i, j, p) == 1:
                # break
        # if s == Fi_p:
            # return i


def init():
    p = choose_p() #选择素数p
    a = 2 #取p的本原元a
    return p,a


def choose_private_key(p,a): # 选择私钥后返回公钥
    d = input(f"在2~{p-2}中选定私钥：")
    E_public = Mutli_big(a, d, p)
    return d,E_public
    
def find_mod_reserve(num1,num2):
    if numpy.gcd(num1,num2) != 1:
        return None
    u1,u2,u3 = 1,0,num1
    v1,v2,v3 = 0,1,num2
    while v3 != 0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%num2


def Hash(message):
    H = 0
    for i in range(len(message)):
        H += message[i]
    return H


def Encryption():
    p,a = init()
    d,E_public = choose_private_key(p, a)
    message = list(input("需要加密的信息："))
    for i in range(len(message)):
        message[i] = ord(message[i])
    k = random.randint(1, p-1)
    while numpy.gcd(k,p-1) != 1:
        k = random.randint(1, p-1)
    r = Mutli_big(a, k, p)
    k_ = find_mod_reserve(k, p-1) # k对p－1的模逆
    H = Hash(message) # 计算hash值
    s = ((H-(int(d)*r))*k_)%(p-1)
    return message,E_public,(p,a),(r,s)


def Dencryption(message,E_public,INIT,VER):
    H_ = Hash(message)
    check1 = (Mutli_big(E_public, VER[0], INIT[0]) * Mutli_big(VER[0], VER[1], INIT[0])) % INIT[0]
    check2 = Mutli_big(INIT[1], H_, INIT[0])
    if check1 == check2:
        return True,message
    return False

def de_message(message):
    re_message = ""
    for i in range(len(message)):
        re_message  += chr(message[i])
    return re_message


def main():
    message,E_public,INIT,VER = Encryption()
    flag = Dencryption(message, E_public, INIT, VER)
    message = de_message(message)

    if flag:
        print(f"签名验证通过！收到的信息为：{message}")
    else:
        print("签名验证不通过！")


if __name__ == "__main__":
    main()
